package cxydmmszl.chapter08.t128;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;

/**
 * <li style="color: red;">Prob</li>
 * 自然数数组的排序
 * <li style="color: green;">Desc</li>
 * 给定一个长度为 N 的整形数组 arr，其中有 N 个互不相等的自然数 1-N 。
 * 请实现 arr 的排序，但是不要把下标 0∼N−1 位置上的数通过直接赋值的方式替换成 1∼N。
 * <br/><br/>[要求]<br/>时间复杂度为 O(n)，空间复杂度为O(1)
 * <br/><br/>备注：<br/>1≤N≤10^5
 * <li style="color: green;">Input</li>
 * 第一行有一个整数 N。表示数组长度
 * 接下来一行有 N 个互不相等的自然数 1-N。
 * <li style="color: green;">Output</li>
 * 输出N个整数表示排序后的结果
 * <li style="color: blue;">Link</li> CD23
 *
 * @author habitplus
 * @since 2021-10-07 20:05
 */
public class Main {
    static StreamTokenizer st =
            new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    static int nextInt() {
        try {
            st.nextToken();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return (int) st.nval;
    }

    public static void main(String[] args) {
        int n = nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = nextInt();
        }

        naturalNumSort(arr);

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            sb.append(arr[i]).append(" ");
        }
        System.out.println(sb.toString());
    }

    private static void naturalNumSort(int[] arr) {
        if (arr == null || arr.length == 0) {
            return;
        }

        int n = arr.length;

        for (int i = 0; i < n; i++) {
            while (arr[i] != i + 1) {
                swap(arr, i, arr[i] - 1);
            }
        }
    }

    private static void swap(int[] arr, int i, int j) {
        int t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }
}
